//
// Created by Administrator on 2022/1/4.
//

#ifndef CPP_LEARNING_BTNODE_HPP
#define CPP_LEARNING_BTNODE_HPP

#define BTNodePosi(T) BTNode<T>*
#include <vector>
using namespace std;

// B树的节点
template <typename T>
struct BTNode{
    BTNodePosi(T) parent;
    vector<T> key;


    vector<BTNodePosi(T)> child;

    BTNode(){
        parent = NULL;
        child_insert(NULL,0);
    }
    BTNode(T e, BTNodePosi(T) lc = NULL, BTNodePosi(T) rc = NULL){
        parent = NULL;
        key.insert(0,e);
        child.insert(0,lc);
        child.insert(1,rc);
        if(lc) lc->parent = this;
        if(rc) rc->parent = this;
    }

    // 返回 <=e的值的索引
    int  search(const T&e);
    int  find(BTNodePosi(T) p);
    void key_insert( const T&e, int r);
    void child_insert( BTNodePosi(T) p, int r);
    void key_erase(int r);
    void child_erase(int r);
};
template <typename T>
void BTNode<T>::key_erase(int r){
    auto i = key.begin();
    int index = 0;
    while (index < r){
        i++;
        index++;
    }
    key.erase(i);
}
template <typename T>
void BTNode<T>::child_erase(int r){
    auto i = child.begin();
    int index = 0;
    while (index < r){
        i++;
        index++;
    }

    child.erase(i);
}
template <typename T>
void BTNode<T>::key_insert(const T&e, int r){
    auto i = key.begin();
    int index = 0;
    while (index < r){
        i++;
        index++;
    }
    key.insert(i, e);
}

template <typename T>
void BTNode<T>::child_insert(BTNodePosi(T) p, int r){
    auto i = child.begin();
    int index = 0;
    while (index < r){
        i++;
        index++;
    }


    child.insert(i, p);
}


/**
 *
 *   1  3  5   7   9
 */

template <typename T>
int  BTNode<T>::search(const T&e){
    int index = -1;
    for(int i=0;i<(this->key).size();i++){
        if(key[i]<=e){
            index = i;
        }else{
            break;
        }
    }
    return index;
}


template <typename T>
int  BTNode<T>::find(BTNodePosi(T) p) {
    int index = -1;
    for (int i = 0; i < (this->child).size(); i++) {
        if (child[i] == p) {
            return i;
        }
    }
    return index;
}
#endif //CPP_LEARNING_BTNODE_HPP
